1. Field of the Invention
The present invention relates to the field of Programmable Logic Arrays (PLAs), Field Programmable Gate Arrays (FPGAs) and Programmable Logic Devices (PLDs). More particularly, the present invention relates to a programmable logic array architecture in which individual logic elements are based on a bit sliceable arithmetic logic unit (ALU), each bit slice being individually programmable to perform low-level Boolean and gate-level operations, as well as higher-level logic and arithmetic functions.
2. Description of the Related Art
FIG. 1 illustrates a programmable logic element 100 used in a conventional programmable logic device. Typically, a logic device includes a two-dimensional array of elements such as element 100 disclosed in U.S. Pat. No. 5,274,581.
As shown, element 100 implements a four-input look-up table 102 which is programmable to produce a desired binary output signal value for each of the sixteen possible combinations of its four binary input signals A, B, C and D. When element 100 is to be used as one stage of a two-input adder or subtracter, a four-input look-up table is much more than is needed to provide just a sum out or carry value. Accordingly, the four-input look-up table is provided as shown in FIG. 1 as two three-input look-up tables 104, 106 so that the one element 100 can provide both a sum out on its normal output, and important precedents to the carry out value on outputs X and Y.
Element 100 also provides further inputs and outputs that enable its use as one place in a binary operation such as addition, subtraction or counting. Specifically, element 100 includes a carry in input, typically from the carry out output of another adjacent logic element. Element 100 further includes a cascade connect input, also typically from another adjacent logic element, which can allow the cascade connect output from the adjacent logic element to be combined with the output of the look-up table in element 100 if desired. In addition to its regular data output from driver 108, element 100 includes a cascade connect output, which typically is applied to the cascade connect input of an adjacent logic element. A carry out signal is similarly applied to the carry in input of another, typically adjacent logic element.
FIG. 2 illustrates how the four-input look-up table 102 of element 100 is realized as two three-input look-up tables 104, 106 using standard logic symbols.
The prior art programmable element, and programmable arrays based thereon, are subject to many drawbacks. For example, when attempting to program structures for performing higher-level functions (such as arithmetic and complex logic operations), many logic elements are required to be combined together, which leads to larger structures and reduced performance, including slow carry propagation. However, this is necessary to maintain the ability to perform lower-.level functions. Further, to allow logic elements to be combined together to perform expanded logic operations, combinational logic must be included in each element, even when such operations are not programmed, thus leading to wasteful circuitry. Moreover, the prior art structures can only be statically programmed to perform different levels of functionality.
What is needed in the art, therefore, is a multi-scale programmable logic device that can be dynamically configured to select different scales of functionality. The present invention fulfills this need, among others.
Accordingly, it is an object of the invention to overcome the abovementioned problems in the prior art.
It is another object of the invention to provide a programmable logic array architecture that allows digital logic to be programmed using both small-scale blocks as well as medium scale blocks.
It is another object of the invention to provide a programmable logic array architecture that can provide multi-scale functionality and maintain high performance.
It is another object of the invention to provide a programmable logic array architecture that can achieve fast carry propagation.
It is another object of the invention to provide a programmable logic array architecture that can provide multi-scale functionality and maintain a single programmable logic element.
It is another object of the invention to provide a programmable logic array architecture that simplifies the programming of complex arithmetic and random logic functions.
It is another object of the invention to provide a programmable logic array architecture that is capable of being dynamically reconfigured to perform different levels of combinational logic functions.
These and other objects of the present invention are fulfilled by a novel architecture for a multi-scale programmable logic array (MSA) to be used in the design of complex digital systems. In the MSA, the static program for the array, stored in configuration memory, defines the functional behavior of each bit-slice circuit and the functional behavior of the ALU controller for a group of bit-slice circuits. These circuits are called the cluster blocks of the architecture. The configuration memory program also controls the flow of logic variables between the cluster blocks.
According to an aspect of the invention, the MSA concept allows digital logic to be programmed using both small-scale blocks (also called gate level blocks) as well as medium scale blocks (also called Register Transfer Level or RTL blocks). Prior art approaches used separate structures to achieve this capability or accepted the reduced performance and increased cost of having a single programmable logic type. The MSA concept is based on a bit sliceable Arithmetic Logic Unit (ALU). Each bit-slice may be programmed to perform a basic Boolean logic operation or to contribute to higher-level functions that are further programmed by an ALU controller circuit. In one embodiment of the invention, the ALU controller level also allows the primitive logic operations computed at the bit-slice level to be combined to perform complex random logic operations. The data shifting capability of this new programmable logic architecture according to another aspect of the invention reduces the complexity of the programmable routing needed to implement shift operations including multiplier arrays. The new array also allows logic variables under program control to dynamically modify the micro-program of each ALU. This technique is called configuration overlay and simplifies the programming of complex arithmetic and random logic functions.